/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/6/7.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 126. 单词接龙 II
 * 给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
 * 每次转换只能改变一个字母。
 * 转换过程中的中间单词必须是字典中的单词。
 *
 * 说明:
 * 如果不存在这样的转换序列，返回一个空列表。
 * 所有单词具有相同的长度。
 * 所有单词只由小写字母组成。
 * 字典中不存在重复的单词。
 * 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
 * 示例 1:
 * 输入:
 * beginWord = "hit",
 * endWord = "cog",
 * wordList = ["hot","dot","dog","lot","log","cog"]
 *
 * 输出:
 * [
 *   ["hit","hot","dot","dog","cog"],
 *   ["hit","hot","lot","log","cog"]
 * ]
 * 示例 2:
 * 输入:
 * beginWord = "hit"
 * endWord = "cog"
 * wordList = ["hot","dot","dog","lot","log"]
 *
 * 输出: []
 *
 * 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
 */
#include <iostream>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
private:
    const int INF = INT32_MAX;                  /* 作为不可能 int 值，实际上能达到... */
    unordered_map<string, int> word_ids_map;    /* id 到 word 映射 */
    vector<string> id_words;                    /* word 到 id 映射 */
    vector<vector<int>> edges;                  /* 每个节点的边 */

public:
    vector<vector<string>> findLadders(const string& beginWord, const string& endWord, vector<string>& wordList) {
        /* 对于本题目，如果我们把 wordList 里的关系看做是一个无向图的话，那么求解最短转换序列就可以
         * 看做是求解单源节点的最短路径了，所以我们可以先对输入进行构图，使用迪杰斯特拉来求解最短路
         * 径。
         */
        /* 首先构图::每个单词的长度是相等的，那么如果单词 A 和单词 B 只有一个单词不同，那么它们则有图联系 */
        /* 对每个 word 进行映射，并分配连续 id */
        int id = 0;
        if(!word_ids_map.count(beginWord)) { /* 未被映射 */
            word_ids_map[beginWord] = id++;
            id_words.push_back(beginWord);
        }
        for(const string& word : wordList) {
            if(!word_ids_map.count(word)) { /* 未被映射 */
                word_ids_map[word] = id++;
                id_words.push_back(word);
            }
        }

        /* 现在检查 endWord 如果不存在在映射中，那么不可能有最短路径 */
        if(!word_ids_map.count(endWord))
            return {};

        /* 构造每个 word 的边集 */
        int id_word_size = id_words.size();
        edges.resize(id_word_size);
        for(int i = 0; i < id_word_size; ++i) {
            for(int j = i + 1; j < id_word_size; ++j) {
                /* 如果这两个单词只有一字之差，那么就存在一条双向边 */
                if(string_diff(id_words[i], id_words[j])) {
                    edges[i].push_back(j);
                    edges[j].push_back(i);
                }
            }
        }

        /* 使用 BFS 寻找 beginWord 的最短单源路径 */
        const int dest = word_ids_map[endWord]; /* 目标 */
        vector<vector<string>> ans;
        int dist[id_word_size];                 /* 距离 */
        for(int &i : dist) {                    /* 初始化为全部 INF */
            i = INF;
        }
        dist[word_ids_map[beginWord]] = 0;      /* 起始节点距离 0 */
        queue<vector<int>> Q;                   /* 查询队列 */
        Q.push(vector<int>{word_ids_map[beginWord]}); /* 源节点入队列，注入链表 */

        /* 只要查询队列不为空，就继续查找 */
        vector<int> v;
        while ( !Q.empty() ) {
            v = Q.front();
            Q.pop();

            int last = v.back();
            if(dest == last) {
                vector<string> ans_tmp;
                ans_tmp.reserve(v.size());
                for(const int num : v) {
                    ans_tmp.push_back(id_words[num]);
                }
                ans.push_back(ans_tmp);
            } else {
                /* 遍历 last 的边，查找所有邻节点，存在 w 中 */
                for(const int w : edges[last]) {
                    if(dist[last] + 1 <= dist[w]) {
                        dist[w] = dist[last] + 1;
                        vector<int> tmp(v);
                        tmp.push_back(w);
                        Q.push(tmp);
                    }
                }
            }

        }


        return ans;
    }

    /* 对比两个字符串的不同(不存在)字符数量，大于 1 返回 false，否则 true */
    static bool string_diff(const string& a, const string& b) {
        int diff = 0;
        for (int i = 0; i < (int) a.size(); i++) {
            if (a[i] != b[i]) {
                if(++diff > 1)      /* 大于 1 直接返回 false */
                    return false;
            }
        }
        /* 能到这，说明 diff == 1 */
        return true;
    }
};


int main() {

//    vector<string> word_list = { "hot", "dot", "dog", "lot", "log", "cog" };
    vector<string> word_list = { "lest","leet","lose","code","lode","robe","lost" };
    Solution sol;
    vector<vector<string>> ans = sol.findLadders("leet", "code", word_list);
    cout << "size::" << ans.size() << endl;
    for(const vector<string>& vec : ans) {
        for(const string& str : vec) {
            cout << str << ", ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}


